<!DOCTYPE html>
<html lang="zh">
<head><meta name="generator" content="Hexo 3.9.0">
    <meta charset="utf-8">
<title>深入解析HashMap源码 - 听到微笑的博客</title>
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">



    <meta name="description" content="​        HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK（Java Developmet Kit）版本的更新，JDK1.8对HashMap底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。">
<meta name="keywords" content="HashMap">
<meta property="og:type" content="article">
<meta property="og:title" content="深入解析HashMap源码">
<meta property="og:url" content="http://www.tianjindong.cn/article/2006.html">
<meta property="og:site_name" content="听到微笑的博客">
<meta property="og:description" content="​        HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK（Java Developmet Kit）版本的更新，JDK1.8对HashMap底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。">
<meta property="og:locale" content="zh-CN">
<meta property="og:image" content="http://www.tianjindong.cn/gallery/thumbnails/c2.jpg">
<meta property="og:updated_time" content="2020-08-22T06:32:33.589Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="深入解析HashMap源码">
<meta name="twitter:description" content="​        HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK（Java Developmet Kit）版本的更新，JDK1.8对HashMap底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。">
<meta name="twitter:image" content="http://www.tianjindong.cn/gallery/thumbnails/c2.jpg">







<link rel="icon" href="/images/favicon.ico">


<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bulma@0.7.2/css/bulma.css">
<link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.4.1/css/all.css">
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Ubuntu:400,600|Source+Code+Pro">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/highlight.js@9.12.0/styles/atom-one-dark.css">


    
    
    
    <style>body>.footer,body>.navbar,body>.section{opacity:0}</style>
    

    
    
    
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/lightgallery@1.6.8/dist/css/lightgallery.min.css">
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/justifiedGallery@3.7.0/dist/css/justifiedGallery.min.css">
    

    
    

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/outdatedbrowser@1.1.5/outdatedbrowser/outdatedbrowser.min.css">


    
    
    
    

<link rel="stylesheet" href="/css/back-to-top.css">


    
    

    
    
<script>
var _hmt = _hmt || [];
(function() {
    var hm = document.createElement("script");
    hm.src = "//hm.baidu.com/hm.js?81f9c1489f84c7a99b0bd377c9fb5de8";
    var s = document.getElementsByTagName("script")[0];
    s.parentNode.insertBefore(hm, s);
})();
</script>

    
    

    
    
<link rel="stylesheet" href="/css/progressbar.css">
<script src="https://cdn.jsdelivr.net/npm/pace-js@1.0.2/pace.min.js"></script>

    
    
    

    
    
    


<link rel="stylesheet" href="/css/style.css">
<link rel="stylesheet" href="/css/iconfont.css">
</head>
<body class="is-2-column">
    <nav class="navbar navbar-main">
    <div class="container">
        <div class="navbar-brand is-flex-center">
            <a class="navbar-item navbar-logo" href="/">
            
                <img src="/images/logo.png" alt="深入解析HashMap源码" height="28">
            
            </a>
        </div>
        <div class="navbar-menu">
            
            <div class="navbar-start">
                
                <a class="navbar-item" href="/">主页</a>
                
                <a class="navbar-item" href="/categories">分类</a>
                
                <a class="navbar-item" href="/tags">标签</a>
                
                <a class="navbar-item" href="/archives">历史</a>
                
                <a class="navbar-item" href="/music.html">音乐</a>
                
                <a class="navbar-item" href="/about.html">关于</a>
                
            </div>
            
            <div class="navbar-end">
                
                
                <a class="navbar-item is-hidden-tablet catalogue" title="目录" href="javascript:;">
                    <i class="fas fa-list-ul"></i>
                </a>
                
                
                <a class="navbar-item search" title="搜索" href="javascript:;">
                    <i class="fas fa-search"></i>
                </a>
                
            </div>
        </div>
    </div>
</nav>
        
    <section class="section">
        <div class="container">
            <div class="columns">
                <div class="column is-8-tablet is-9-desktop is-9-widescreen has-order-2 column-main"><div class="card">
    
    <div class="card-image">
        <span class="image is-7by1">
            <img class="thumbnail" src="/gallery/thumbnails/c2.jpg" alt="深入解析HashMap源码">
        </span>
    </div>
    
    <div class="card-content article ">
        
        <div class="level article-meta is-size-7 is-uppercase is-mobile is-overflow-x-auto">
            <div class="level-left">
                <time class="level-item has-text-grey" datetime="2019-08-15T02:04:47.000Z">2019-08-15</time>
                
                <div class="level-item">
                <a class="has-link-grey -link" href="/categories/Java基础/">Java基础</a>
                </div>
                
                
                <span class="level-item has-text-grey">
                    
                    
                    27 分钟 读完 (大约 4103 个字)
                </span>
                
                
            </div>
        </div>
        
        <h1 class="title is-size-3 is-size-4-mobile has-text-weight-normal">
            
                深入解析HashMap源码
            
        </h1>
        <div class="content">
            <p>​        HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK（Java Developmet Kit）版本的更新，JDK1.8对HashMap底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。<a id="more"></a></p>
<p>​        Java为数据结构中的映射定义了一个接口java.util.Map，此接口主要有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap，类继承关系如下图所示：</p>


<p>下面针对各个实现类的特点做一些说明：</p>
<p>(1) HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。</p>
<p>(2) Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。</p>
<p>(3) LinkedHashMap：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。</p>
<p>(4) TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。</p>
<p><code>对于上述四种Map类型的类，要求映射中的key是不可变对象</code>。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。</p>
<h2 id="HashMap的基本原理"><a href="#HashMap的基本原理" class="headerlink" title="HashMap的基本原理"></a><strong>HashMap的基本原理</strong></h2><p>​        如果小伙伴们对HashMap的基本原理还不熟悉，建议大家参考 <a href="https://mp.weixin.qq.com/s/HzRH9ZJYmidzW5jrMvEi4w" target="_blank" rel="noopener">漫画：什么是HashMap？</a>一文。这里对基本原理进行简单的梳理：</p>
<p>​        HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做<strong>Entry</strong>。这些个键值对（Entry）分散存储在一个数组当中（这个数组被称为Hash桶数组），这个数组就是HashMap的基础。</p>


<p>​        那么我们如何将对象按照key的值放入到数组中去呢？这里我们就需要借助Hash函数，Hash函数可以将任何一个对象转换为一个int类型的值，但是这还不能将元素插入到数组中，因为数组的容量有限，而int类型的值非常大，我们不可能将int类型的Hash值与数组的元素一一对应，那么解决这种问题最简单的方法就是取模（%），将<code>Hash值%数组容量</code>就会得到一个不大于数组容量的一个数值，就可以将元素插入到数组中。</p>
<p>​        但是，因为HashMap中数组的长度是有限的，当插入的Entry越来越多时，再完美的Hash函数也难免会出现index冲突的情况（Hash冲突就是两个不同Entry计算出来的数组索引值相同）。那么解决Hash冲突最简单的方法采用拉链法，也就是将冲突的Entry以链表的形式存在。</p>
<p>​    </p>
<p>​        在JDK7之前，HashMap解决Hash冲突时都是采用拉链法解决的；而在JDK8开始，HashMap采用链表+红黑树相结合的方式解决的，具体实现原理在后序源码讲解中体现。</p>
<p>​        当HashMap中的数组中保存的Entry太多后，Hash冲突的可能性不断增大，这样会大大降低HashMap的执行效率，所以HashMap引入了扩容机制。这里就需要了解加载因子（负载因子）的概念，当元素个数大&gt;数组容量*加载因子时就会触发扩容，扩容时HashMap中的数组增加至原来两倍，将原Map中的数组重新散列到新的数组中去，至此完成了扩容操作。</p>
<h2 id="HashMap源码分析"><a href="#HashMap源码分析" class="headerlink" title="HashMap源码分析"></a><strong>HashMap源码分析</strong></h2><h3 id="HashMap中的常量值"><a href="#HashMap中的常量值" class="headerlink" title="HashMap中的常量值"></a><strong>HashMap中的常量值</strong></h3><figure class="highlight java hljs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="hljs-comment">/**</span></span><br><span class="line"><span class="hljs-comment">    * 默认的数组容量为16</span></span><br><span class="line"><span class="hljs-comment">    */</span></span><br><span class="line">   <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> DEFAULT_INITIAL_CAPACITY = <span class="hljs-number">1</span> &lt;&lt; <span class="hljs-number">4</span>; <span class="hljs-comment">// aka 16</span></span><br><span class="line"></span><br><span class="line">   <span class="hljs-comment">/**</span></span><br><span class="line"><span class="hljs-comment">    *	数组的最大容量。在后面我们会将每一个数组元素看成一个桶，因为数组元素在后面可能连接的是一个链表或者是一颗树。</span></span><br><span class="line"><span class="hljs-comment">    */</span></span><br><span class="line">   <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> MAXIMUM_CAPACITY = <span class="hljs-number">1</span> &lt;&lt; <span class="hljs-number">30</span>;</span><br><span class="line"></span><br><span class="line">   <span class="hljs-comment">/**</span></span><br><span class="line"><span class="hljs-comment">    * 默认的加载因子（负载因子）为0.75</span></span><br><span class="line"><span class="hljs-comment">    */</span></span><br><span class="line">   <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">float</span> DEFAULT_LOAD_FACTOR = <span class="hljs-number">0.75f</span>;</span><br><span class="line"></span><br><span class="line">   <span class="hljs-comment">/**</span></span><br><span class="line"><span class="hljs-comment">    * 当链表长度到达TREEIFY_THRESHOLD时将链表转换为红黑树，也就是说链表最长为7。</span></span><br><span class="line"><span class="hljs-comment">    */</span></span><br><span class="line">   <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> TREEIFY_THRESHOLD = <span class="hljs-number">8</span>;</span><br><span class="line"></span><br><span class="line">    <span class="hljs-comment">/**</span></span><br><span class="line"><span class="hljs-comment">    * . 桶的链表还原阈值：即 红黑树转为链表的阈值，当在扩容（resize（））时（此时HashMap的数据存储位置会重新计算），在重新计算存储位置后，当原有的红黑树内数量 &lt; 6时，则将 红黑树转换成链表</span></span><br><span class="line"><span class="hljs-comment">    */</span></span><br><span class="line">   <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> UNTREEIFY_THRESHOLD = <span class="hljs-number">6</span>;</span><br></pre></td></tr></table></figure>

<p>​        上面部分常量值有可能不能完全理解，我们这里只做一些了解即可。</p>
<h3 id="HashMap中几个关键字段"><a href="#HashMap中几个关键字段" class="headerlink" title="HashMap中几个关键字段"></a><strong>HashMap中几个关键字段</strong></h3><figure class="highlight java hljs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="hljs-keyword">int</span> threshold;             <span class="hljs-comment">// 所能容纳的key-value对极限 (阈值)</span></span><br><span class="line"><span class="hljs-keyword">final</span> <span class="hljs-keyword">float</span> loadFactor;    <span class="hljs-comment">// 负载因子 </span></span><br><span class="line"><span class="hljs-keyword">int</span> modCount;  <span class="hljs-comment">//用于迭代的快速失败机制</span></span><br><span class="line"><span class="hljs-keyword">int</span> size;  	<span class="hljs-comment">//HashMap中实际存在的键值对数量</span></span><br></pre></td></tr></table></figure>

<ul>
<li><strong>threshold和loadFactor</strong>：Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。</li>
<li><strong>size</strong>：这个字段其实很好理解，就是HashMap中实际存在的键值对数量。注意和table的长度length、容纳最大键值对数量threshold的区别。</li>
<li><strong>modCount</strong>：这个字段主要用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化</li>
</ul>
<h3 id="构造函数分析"><a href="#构造函数分析" class="headerlink" title="构造函数分析"></a><strong>构造函数分析</strong></h3><figure class="highlight java hljs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="hljs-comment">/**</span></span><br><span class="line"><span class="hljs-comment">    * <span class="hljs-doctag">@param</span>  initialCapacity HashMap初始化桶的个数（数组的容量）</span></span><br><span class="line"><span class="hljs-comment">    * <span class="hljs-doctag">@param</span>  loadFactor      加载因子小于0抛出异常</span></span><br><span class="line"><span class="hljs-comment">    */</span></span><br><span class="line">   <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">HashMap</span><span class="hljs-params">(<span class="hljs-keyword">int</span> initialCapacity, <span class="hljs-keyword">float</span> loadFactor)</span> </span>&#123;</span><br><span class="line">   	<span class="hljs-comment">//如果initialCapacity小于0抛出异常</span></span><br><span class="line">       <span class="hljs-keyword">if</span> (initialCapacity &lt; <span class="hljs-number">0</span>)</span><br><span class="line">           <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IllegalArgumentException(<span class="hljs-string">"Illegal initial capacity: "</span> + initialCapacity);</span><br><span class="line">       <span class="hljs-comment">//如果initialCapacity大于最大容量，则将初始化容量设为最大值</span></span><br><span class="line">       <span class="hljs-keyword">if</span> (initialCapacity &gt; MAXIMUM_CAPACITY)</span><br><span class="line">           initialCapacity = MAXIMUM_CAPACITY;</span><br><span class="line">       <span class="hljs-comment">//当加载因子小于等于0</span></span><br><span class="line">       <span class="hljs-keyword">if</span> (loadFactor &lt;= <span class="hljs-number">0</span> || Float.isNaN(loadFactor))</span><br><span class="line">           <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IllegalArgumentException(<span class="hljs-string">"Illegal load factor: "</span> +</span><br><span class="line">                                              loadFactor);</span><br><span class="line">       <span class="hljs-keyword">this</span>.loadFactor = loadFactor;</span><br><span class="line">       <span class="hljs-comment">//如果用户传入的initialCapacity值不是2的幂，那么返回一个不小于它的2的幂</span></span><br><span class="line">       <span class="hljs-keyword">this</span>.threshold = tableSizeFor(initialCapacity);</span><br><span class="line">   &#125;</span><br></pre></td></tr></table></figure>

<p>​    构造函数中传入了initialCapacity，loadFactor。</p>
<p>​    initialCapacity表示HashMap中桶的个数。</p>
<p>​    loadFactor是HashMap的加载因子（负载因子），负载因子决定HashMap的扩容时机，如果HashMap中存储的Entry数量大于等于 <code>当前数组容量*加载因子时</code>就会触发数组的扩容操作。举例来说：假如当前数组容量为16，加载因子为0.75，那么此时数组中最大的元素个数为16*0.75=12。</p>
<h4 id="tableSizeFor方法的作用"><a href="#tableSizeFor方法的作用" class="headerlink" title="tableSizeFor方法的作用"></a><strong>tableSizeFor方法的作用</strong></h4><p>​    在构造函数中调用了一个名为tableSizeFor方法，它将用户传入的初始容量转换为一个不小该值的2的幂值。例如：传入initialCapacity=11，他返回的是initialCapacity=16。这样做的目的到底是为什么呢？</p>
<p>​    前面说到了元素定位时会使用取模运算，实际上这种算法效率非常低，为了实现更加高效的算法，HashMap采用位运算的方式：</p>
<p>​    <strong>index =  HashCode（Key） &amp;  （Length - 1）</strong> </p>
<p>下面我们以值为“book”的Key来演示整个过程：</p>
<ol>
<li>计算book的hashcode，结果为十进制的3029737，二进制的101110001110101110 1001。</li>
<li>假定HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111。</li>
<li>把以上两个结果做<strong>与运算</strong>，101110001110101110 1001 &amp; 1111 = 1001，十进制是9，所以 index=9。</li>
</ol>
<p>采用位运算得到的结果与取模运算的效果完全相同，但是这样做的前提就是Length必须是2的幂。这也就是为什么HashMap会定义tableSizeFor方法返回容量的2次幂值。</p>
<h3 id="静态内部类"><a href="#静态内部类" class="headerlink" title="静态内部类"></a><strong>静态内部类</strong></h3><figure class="highlight java hljs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br></pre></td><td class="code"><pre><span class="line"><span class="hljs-comment">// Node实现了Map.Entry&lt;K,V&gt;接口，也就是说Node实际上就是我们前面提到的Entry</span></span><br><span class="line"><span class="hljs-keyword">static</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Node</span>&lt;<span class="hljs-title">K</span>,<span class="hljs-title">V</span>&gt; <span class="hljs-keyword">implements</span> <span class="hljs-title">Map</span>.<span class="hljs-title">Entry</span>&lt;<span class="hljs-title">K</span>,<span class="hljs-title">V</span>&gt; </span>&#123;</span><br><span class="line">        <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> hash;<span class="hljs-comment">//保存当前Entry key的hash值，由于后面会多次使用该Hash值，避免重复计算</span></span><br><span class="line">        <span class="hljs-keyword">final</span> K key; </span><br><span class="line">        V value;</span><br><span class="line">        Node&lt;K,V&gt; next;<span class="hljs-comment">//指向链表下一个节点</span></span><br><span class="line"></span><br><span class="line">        Node(<span class="hljs-keyword">int</span> hash, K key, V value, Node&lt;K,V&gt; next) &#123;</span><br><span class="line">            <span class="hljs-keyword">this</span>.hash = hash;</span><br><span class="line">            <span class="hljs-keyword">this</span>.key = key;</span><br><span class="line">            <span class="hljs-keyword">this</span>.value = value;</span><br><span class="line">            <span class="hljs-keyword">this</span>.next = next;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">final</span> K <span class="hljs-title">getKey</span><span class="hljs-params">()</span>        </span>&#123; <span class="hljs-keyword">return</span> key; &#125;</span><br><span class="line">        <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">final</span> V <span class="hljs-title">getValue</span><span class="hljs-params">()</span>      </span>&#123; <span class="hljs-keyword">return</span> value; &#125;</span><br><span class="line">        <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">final</span> String <span class="hljs-title">toString</span><span class="hljs-params">()</span> </span>&#123; <span class="hljs-keyword">return</span> key + <span class="hljs-string">"="</span> + value; &#125;</span><br><span class="line"></span><br><span class="line">        <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> <span class="hljs-title">hashCode</span><span class="hljs-params">()</span> </span>&#123;</span><br><span class="line">            <span class="hljs-keyword">return</span> Objects.hashCode(key) ^ Objects.hashCode(value);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">final</span> V <span class="hljs-title">setValue</span><span class="hljs-params">(V newValue)</span> </span>&#123;</span><br><span class="line">            V oldValue = value;</span><br><span class="line">            value = newValue;</span><br><span class="line">            <span class="hljs-keyword">return</span> oldValue;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">equals</span><span class="hljs-params">(Object o)</span> </span>&#123;</span><br><span class="line">            <span class="hljs-keyword">if</span> (o == <span class="hljs-keyword">this</span>)</span><br><span class="line">                <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;</span><br><span class="line">            <span class="hljs-keyword">if</span> (o <span class="hljs-keyword">instanceof</span> Map.Entry) &#123;</span><br><span class="line">                Map.Entry&lt;?,?&gt; e = (Map.Entry&lt;?,?&gt;)o;</span><br><span class="line">                <span class="hljs-keyword">if</span> (Objects.equals(key, e.getKey()) &amp;&amp;</span><br><span class="line">                    Objects.equals(value, e.getValue()))</span><br><span class="line">                    <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>​        看完构造函数和类的常量值以及Entry的结构后，我们就以HashMap中put方法入手，看看HashMap中的底层原理。</p>
<h3 id="put方法源码"><a href="#put方法源码" class="headerlink" title="put方法源码"></a><strong>put方法源码</strong></h3><figure class="highlight java hljs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br></pre></td><td class="code"><pre><span class="line"><span class="hljs-function"><span class="hljs-keyword">public</span> V <span class="hljs-title">put</span><span class="hljs-params">(K key, V value)</span> </span>&#123;</span><br><span class="line">       <span class="hljs-keyword">return</span> putVal(hash(key), key, value, <span class="hljs-keyword">false</span>, <span class="hljs-keyword">true</span>);</span><br><span class="line">   &#125;</span><br><span class="line"></span><br><span class="line"><span class="hljs-comment">/**</span></span><br><span class="line"><span class="hljs-comment">* 计算key的hash值，该hash算法调用了Obejct的hashcode</span></span><br><span class="line"><span class="hljs-comment">* 返回的是key.hashCode()&amp;(key.hashCode()&gt;&gt;&gt;16),其中&gt;&gt;&gt;代表无符号右移</span></span><br><span class="line"><span class="hljs-comment">**/</span></span><br><span class="line"><span class="hljs-function"><span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> <span class="hljs-title">hash</span><span class="hljs-params">(Object key)</span> </span>&#123;</span><br><span class="line">       <span class="hljs-keyword">int</span> h;</span><br><span class="line">       <span class="hljs-keyword">return</span> (key == <span class="hljs-keyword">null</span>) ? <span class="hljs-number">0</span> : (h = key.hashCode()) ^ (h &gt;&gt;&gt; <span class="hljs-number">16</span>);</span><br><span class="line">   &#125;</span><br><span class="line"></span><br><span class="line">   <span class="hljs-function"><span class="hljs-keyword">final</span> V <span class="hljs-title">putVal</span><span class="hljs-params">(<span class="hljs-keyword">int</span> hash, K key, V value, <span class="hljs-keyword">boolean</span> onlyIfAbsent,</span></span></span><br><span class="line"><span class="hljs-function"><span class="hljs-params">                  <span class="hljs-keyword">boolean</span> evict)</span> </span>&#123;</span><br><span class="line">       Node&lt;K,V&gt;[] tab; </span><br><span class="line">       Node&lt;K,V&gt; p; </span><br><span class="line">       <span class="hljs-keyword">int</span> n, i;</span><br><span class="line">       <span class="hljs-comment">//将Map内部的table数组赋给局部变量tab，如果table为空或者大小为0，则使用resize进行扩容</span></span><br><span class="line">       <span class="hljs-keyword">if</span> ((tab = table) == <span class="hljs-keyword">null</span> || (n = tab.length) == <span class="hljs-number">0</span>)</span><br><span class="line">           n = (tab = resize()).length;</span><br><span class="line"></span><br><span class="line">    	<span class="hljs-comment">/**</span></span><br><span class="line"><span class="hljs-comment">    	 * n-1&amp;hash的效果就是 hash%n （因为HashMap中封装的数组的长度都是2的幂(默认16)）</span></span><br><span class="line"><span class="hljs-comment">    	 * 如果数组对应位置没有元素（没有发生Hash冲突），则新建一个Node元素，放入该数组位置</span></span><br><span class="line"><span class="hljs-comment">    	 */</span></span><br><span class="line">       <span class="hljs-keyword">if</span> ((p = tab[i = (n - <span class="hljs-number">1</span>) &amp; hash]) == <span class="hljs-keyword">null</span>)</span><br><span class="line">           tab[i] = newNode(hash, key, value, <span class="hljs-keyword">null</span>);</span><br><span class="line"></span><br><span class="line">       <span class="hljs-comment">/**</span></span><br><span class="line"><span class="hljs-comment">        * 发生Hash冲突后的处理</span></span><br><span class="line"><span class="hljs-comment">        */</span></span><br><span class="line">       <span class="hljs-keyword">else</span> &#123;</span><br><span class="line">           Node&lt;K,V&gt; e; K k;</span><br><span class="line">           <span class="hljs-keyword">if</span> (p.hash == hash &amp;&amp;</span><br><span class="line">               ((k = p.key) == key || (key != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">               e = p;</span><br><span class="line">           <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (p <span class="hljs-keyword">instanceof</span> TreeNode)</span><br><span class="line">               e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(<span class="hljs-keyword">this</span>, tab, hash, key, value);</span><br><span class="line">           <span class="hljs-keyword">else</span> &#123;</span><br><span class="line">           	<span class="hljs-comment">//如果此时解决Hash冲突的数据结构为链表，则遍历到链表尾部</span></span><br><span class="line">               <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> binCount = <span class="hljs-number">0</span>; ; ++binCount) &#123;</span><br><span class="line">                   <span class="hljs-keyword">if</span> ((e = p.next) == <span class="hljs-keyword">null</span>) &#123;</span><br><span class="line">                   	<span class="hljs-comment">//向链表中添加新元素</span></span><br><span class="line">                       p.next = newNode(hash, key, value, <span class="hljs-keyword">null</span>);</span><br><span class="line">                       <span class="hljs-comment">//如果新元素未加入之前，链表长度大于等于7了则需要将链表转换为红黑树了，换句话说加入新元素后链表长度大于等于8了，就转成红黑树。</span></span><br><span class="line">                       <span class="hljs-keyword">if</span> (binCount &gt;= TREEIFY_THRESHOLD - <span class="hljs-number">1</span>) <span class="hljs-comment">// -1 for 1st</span></span><br><span class="line">                           treeifyBin(tab, hash);<span class="hljs-comment">//将链表转换为红黑树</span></span><br><span class="line">                       <span class="hljs-comment">//跳出循环</span></span><br><span class="line">                       <span class="hljs-keyword">break</span>;</span><br><span class="line">                   &#125;</span><br><span class="line">                   <span class="hljs-comment">//判断key是否相等</span></span><br><span class="line">                   <span class="hljs-comment">//这里的条件判断显示出HashMap允许一个key==null的键值对存储</span></span><br><span class="line">                   <span class="hljs-keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">                       ((k = e.key) == key || (key != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">                       <span class="hljs-keyword">break</span>;</span><br><span class="line">                   p = e;</span><br><span class="line">               &#125;</span><br><span class="line">           &#125;</span><br><span class="line">           <span class="hljs-comment">//如果找到了一个相同的key，则根据onlyIfAbsent判断是否需要替换旧的value。</span></span><br><span class="line">           <span class="hljs-comment">//onlyIfAbsent为true时代表不替换原先元素。</span></span><br><span class="line">           <span class="hljs-keyword">if</span> (e != <span class="hljs-keyword">null</span>) &#123; <span class="hljs-comment">// existing mapping for key</span></span><br><span class="line">               V oldValue = e.value;</span><br><span class="line">               <span class="hljs-keyword">if</span> (!onlyIfAbsent || oldValue == <span class="hljs-keyword">null</span>)</span><br><span class="line">                   e.value = value;</span><br><span class="line">               afterNodeAccess(e);</span><br><span class="line">               <span class="hljs-keyword">return</span> oldValue;</span><br><span class="line">           &#125;</span><br><span class="line">       &#125;</span><br><span class="line"></span><br><span class="line">       <span class="hljs-comment">//被修改的次数，fast-fail机制</span></span><br><span class="line">       ++modCount;</span><br><span class="line"></span><br><span class="line">       <span class="hljs-comment">//如果HashMap中存储的节点数量是否到达了扩容的阈值</span></span><br><span class="line">       <span class="hljs-keyword">if</span> (++size &gt; threshold)</span><br><span class="line">       	<span class="hljs-comment">//进行扩容</span></span><br><span class="line">           resize();</span><br><span class="line">       afterNodeInsertion(evict);</span><br><span class="line">       <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;</span><br><span class="line">   &#125;</span><br></pre></td></tr></table></figure>

<h3 id="resize方法"><a href="#resize方法" class="headerlink" title="resize方法"></a><strong>resize方法</strong></h3><figure class="highlight java hljs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br></pre></td><td class="code"><pre><span class="line"><span class="hljs-comment">/**</span></span><br><span class="line"><span class="hljs-comment">     * 初始化Map中的Node数组，如果已经初始化则进行扩容操作</span></span><br><span class="line"><span class="hljs-comment">     */</span></span><br><span class="line">    <span class="hljs-keyword">final</span> Node&lt;K,V&gt;[] resize() &#123;</span><br><span class="line">        Node&lt;K,V&gt;[] oldTab = table;</span><br><span class="line">        <span class="hljs-comment">//获取数组的原始大小</span></span><br><span class="line">        <span class="hljs-keyword">int</span> oldCap = (oldTab == <span class="hljs-keyword">null</span>) ? <span class="hljs-number">0</span> : oldTab.length;</span><br><span class="line">        <span class="hljs-comment">//获取原始阈值</span></span><br><span class="line">        <span class="hljs-keyword">int</span> oldThr = thresholds;</span><br><span class="line">        <span class="hljs-comment">//用于记录新容量和新阈值</span></span><br><span class="line">        <span class="hljs-keyword">int</span> newCap, newThr = <span class="hljs-number">0</span>;</span><br><span class="line">        <span class="hljs-comment">//如果原始容量大于0，则代表当前Map已经初始化过了，则应该进行扩容操作</span></span><br><span class="line">        <span class="hljs-keyword">if</span> (oldCap &gt; <span class="hljs-number">0</span>) &#123;</span><br><span class="line">            <span class="hljs-keyword">if</span> (oldCap &gt;= MAXIMUM_CAPACITY) &#123;</span><br><span class="line">                threshold = Integer.MAX_VALUE;</span><br><span class="line">                <span class="hljs-keyword">return</span> oldTab;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="hljs-comment">//将新的容量设为原先的两倍（oldCap&lt;&lt;1）</span></span><br><span class="line">            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ((newCap = oldCap &lt;&lt; <span class="hljs-number">1</span>) &lt; MAXIMUM_CAPACITY &amp;&amp;</span><br><span class="line">                     oldCap &gt;= DEFAULT_INITIAL_CAPACITY)</span><br><span class="line">            	<span class="hljs-comment">//将阈值也设为原先的两倍</span></span><br><span class="line">                newThr = oldThr &lt;&lt; <span class="hljs-number">1</span>; <span class="hljs-comment">// double threshold</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="hljs-comment">// 初始化数组走这里</span></span><br><span class="line">        <span class="hljs-comment">// 如果构造函数定义了数组初始容量</span></span><br><span class="line">        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (oldThr &gt; <span class="hljs-number">0</span>) <span class="hljs-comment">// initial capacity was placed in threshold</span></span><br><span class="line">            newCap = oldThr;</span><br><span class="line"></span><br><span class="line">        <span class="hljs-comment">// 如果构造函数没有定义初始容量</span></span><br><span class="line">        <span class="hljs-keyword">else</span> &#123;               <span class="hljs-comment">// zero initial threshold signifies using defaults</span></span><br><span class="line">        	<span class="hljs-comment">//初始化数组容量（16）</span></span><br><span class="line">            newCap = DEFAULT_INITIAL_CAPACITY;	</span><br><span class="line">            <span class="hljs-comment">//初始化阈值（16*0.75 = 12）</span></span><br><span class="line">            newThr = (<span class="hljs-keyword">int</span>)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="hljs-comment">// 构造函数中定义了初始容量 在这里计算阈值</span></span><br><span class="line">        <span class="hljs-keyword">if</span> (newThr == <span class="hljs-number">0</span>) &#123;</span><br><span class="line">            <span class="hljs-keyword">float</span> ft = (<span class="hljs-keyword">float</span>)newCap * loadFactor;</span><br><span class="line">            newThr = (newCap &lt; MAXIMUM_CAPACITY &amp;&amp; ft &lt; (<span class="hljs-keyword">float</span>)MAXIMUM_CAPACITY ?</span><br><span class="line">                      (<span class="hljs-keyword">int</span>)ft : Integer.MAX_VALUE);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="hljs-comment">// 阈值</span></span><br><span class="line">        threshold = newThr;</span><br><span class="line">        <span class="hljs-meta">@SuppressWarnings</span>(&#123;<span class="hljs-string">"rawtypes"</span>,<span class="hljs-string">"unchecked"</span>&#125;)</span><br><span class="line"></span><br><span class="line">        <span class="hljs-comment">//创建一个新的数组，可用于初始化，也可用于扩容</span></span><br><span class="line">        Node&lt;K,V&gt;[] newTab = (Node&lt;K,V&gt;[])<span class="hljs-keyword">new</span> Node[newCap];</span><br><span class="line">        table = newTab;</span><br><span class="line">        <span class="hljs-keyword">if</span> (oldTab != <span class="hljs-keyword">null</span>) &#123;</span><br><span class="line">        	<span class="hljs-comment">//遍历旧数组，将就数组中的元素，重新散列到新数组中去</span></span><br><span class="line">            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; oldCap; ++j) &#123;</span><br><span class="line">            	<span class="hljs-comment">//e表示数组上的节点</span></span><br><span class="line">                Node&lt;K,V&gt; e;</span><br><span class="line">                <span class="hljs-keyword">if</span> ((e = oldTab[j]) != <span class="hljs-keyword">null</span>) &#123;</span><br><span class="line">                	<span class="hljs-comment">//把头节点置为空</span></span><br><span class="line">                    oldTab[j] = <span class="hljs-keyword">null</span>;</span><br><span class="line">                    <span class="hljs-comment">//当就数组中头元素没有链表子节点时，直接散列该元素</span></span><br><span class="line">                    <span class="hljs-keyword">if</span> (e.next == <span class="hljs-keyword">null</span>)</span><br><span class="line">                        newTab[e.hash &amp; (newCap - <span class="hljs-number">1</span>)] = e;</span><br><span class="line"></span><br><span class="line">                    <span class="hljs-comment">//如果数组头元素下面还有其他子节点，且子节点是树结构</span></span><br><span class="line">                    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (e <span class="hljs-keyword">instanceof</span> TreeNode)</span><br><span class="line">                        ((TreeNode&lt;K,V&gt;)e).split(<span class="hljs-keyword">this</span>, newTab, j, oldCap);</span><br><span class="line"></span><br><span class="line">                    <span class="hljs-comment">//如果是一个链表</span></span><br><span class="line">                    <span class="hljs-keyword">else</span> &#123; <span class="hljs-comment">// preserve order</span></span><br><span class="line">                        Node&lt;K,V&gt; loHead = <span class="hljs-keyword">null</span>, loTail = <span class="hljs-keyword">null</span>;</span><br><span class="line">                        Node&lt;K,V&gt; hiHead = <span class="hljs-keyword">null</span>, hiTail = <span class="hljs-keyword">null</span>;</span><br><span class="line">                        Node&lt;K,V&gt; next;</span><br><span class="line">                        <span class="hljs-keyword">do</span> &#123;</span><br><span class="line">                            next = e.next;</span><br><span class="line">                            <span class="hljs-comment">// 还是原来的索引值</span></span><br><span class="line">                            <span class="hljs-keyword">if</span> ((e.hash &amp; oldCap) == <span class="hljs-number">0</span>) &#123;</span><br><span class="line">                                <span class="hljs-keyword">if</span> (loTail == <span class="hljs-keyword">null</span>)</span><br><span class="line">                                    loHead = e;</span><br><span class="line">                                <span class="hljs-keyword">else</span></span><br><span class="line">                                    loTail.next = e;</span><br><span class="line">                                loTail = e;</span><br><span class="line">                            &#125;</span><br><span class="line">                            <span class="hljs-comment">// 不是原来的索引值了 需要迁移</span></span><br><span class="line">                            <span class="hljs-keyword">else</span> &#123;</span><br><span class="line">                                <span class="hljs-keyword">if</span> (hiTail == <span class="hljs-keyword">null</span>)</span><br><span class="line">                                    hiHead = e;</span><br><span class="line">                                <span class="hljs-keyword">else</span></span><br><span class="line">                                    hiTail.next = e;</span><br><span class="line">                                hiTail = e;</span><br><span class="line">                            &#125;</span><br><span class="line">                        &#125; <span class="hljs-keyword">while</span> ((e = next) != <span class="hljs-keyword">null</span>);</span><br><span class="line">                        <span class="hljs-keyword">if</span> (loTail != <span class="hljs-keyword">null</span>) &#123;</span><br><span class="line">                        	<span class="hljs-comment">//将尾节点的next指针置为空</span></span><br><span class="line">                            loTail.next = <span class="hljs-keyword">null</span>;</span><br><span class="line">                            <span class="hljs-comment">//将链接的不移动链表放到原索引位置</span></span><br><span class="line">                            newTab[j] = loHead;</span><br><span class="line">                        &#125;</span><br><span class="line">                        <span class="hljs-keyword">if</span> (hiTail != <span class="hljs-keyword">null</span>) &#123;</span><br><span class="line">                            hiTail.next = <span class="hljs-keyword">null</span>;</span><br><span class="line">                            <span class="hljs-comment">//将链接的移动链表放到新的索引位置</span></span><br><span class="line">                            newTab[j + oldCap] = hiHead;</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="hljs-keyword">return</span> newTab;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>

<p>从66行开始代码进入了链表元素的迁移工作，<code>loHead</code>和<code>loTail</code>两个节点分别记录不需要移动的链表的头部和尾部，<code>hiHead</code>和<code>hiTail</code>分别记录需要移动的链表头部和尾部。</p>
<p>假设在扩容的时候某个数组下有这样一个链表 :</p>


<p>其中，假设天蓝色部分的不需要挪动，红色部分的需要挪动</p>
<p>第一步 : 建立<code>loHead</code> <code>loTail</code> <code>hiHead</code> <code>hiTail</code>四个节点</p>
<p>第二步 ：</p>


<p>第三步 :</p>


<p>…第N步：</p>


<h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a><strong>总结</strong></h2><p><strong>下图是美团技术团队的put函数的流程总结</strong> ：</p>


<p><strong>参考文章</strong>：</p>
<p><a href="https://mp.weixin.qq.com/s/HzRH9ZJYmidzW5jrMvEi4w" target="_blank" rel="noopener">漫画：什么是HashMap</a></p>
<p><a href="https://www.jianshu.com/p/8244a21bd2b4" target="_blank" rel="noopener">HashMap源码分析——put和get（一）</a></p>
<p><a href="https://tech.meituan.com/2016/06/24/java-hashmap.html" target="_blank" rel="noopener">美团HashMap技术博客</a></p>
<p><a href="https://www.2cto.com/kf/201505/401433.html?ysxejs=ujfxo2" target="_blank" rel="noopener">红黑联盟，Java类集框架之HashMap(JDK1.8)源码剖析，2015</a></p>
<p><a href="https://blog.csdn.net/v_july_v/article/details/6105630" target="_blank" rel="noopener">CSDN博客频道， 教你初步了解红黑树，2010</a></p>

        </div>
        
        <div class="level is-size-7 is-uppercase">
            <div class="level-start">
                <div class="level-item">
                    <span class="is-size-6 has-text-grey has-mr-7">#</span>
                    <a class="has-link-grey -link" href="/tags/HashMap/">HashMap</a>
                </div>
            </div>
        </div>
        
        
        
        
<div class="sharethis-inline-share-buttons"></div>
<script type="text/javascript" src="//platform-api.sharethis.com/js/sharethis.js#property=5d1b4ddd55a8b200110cdf62&amp;product=social-ab" async="async"></script>

        
    </div>
</div>



<div class="card">
    <div class="card-content">
        <h3 class="menu-label has-text-centered">喜欢这篇文章？打赏一下作者吧</h3>
        <div class="buttons is-centered">
            
                
<a class="button is-info donate">
    <span class="icon is-small">
        <i class="fab fa-alipay"></i>
    </span>
    <span>支付宝</span>
    <div class="qrcode"><img src="/images/alipay.jpg" alt="支付宝"></div>
</a>

                
                
<a class="button is-success donate">
    <span class="icon is-small">
        <i class="fab fa-weixin"></i>
    </span>
    <span>微信</span>
    <div class="qrcode"><img src="/images/wechat.png" alt="微信"></div>
</a>

                
        </div>
    </div>
</div>



<div class="card card-transparent">
    <div class="level post-navigation is-flex-wrap is-mobile">
        
        <div class="level-end">
            <a class="level level-item has-link-grey  article-nav-next" href="/article/17488.html">
                <i class="level-item fas fa-chevron-left"></i>
                <span class="level-item">真正理解Maven的聚合与继承</span>
            </a>
        </div>
        
        
        <div class="level-start">
            <a class="level level-item has-link-grey  article-nav-prev" href="/article/59694.html">
                <span class="level-item">深入解析LinkedHashMap</span>
                <i class="level-item fas fa-chevron-right"></i>
            </a>
        </div>
        
    </div>
</div>



<div class="card">
    <div class="card-content">
        <h3 class="title is-5 has-text-weight-normal">评论</h3>
        
<div id="comment-container"></div>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/gitalk@1.4.1/dist/gitalk.css">
<script src="https://cdn.jsdelivr.net/npm/gitalk@1.4.1/dist/gitalk.min.js"></script>
<script>
    var gitalk = new Gitalk({
        clientID: 'a362d7e659d5da0b4c24',
        clientSecret: 'bfd2817b484ba4d45ad14e44bbf993fa353a4f2d',
        id: '7bee6f98bdbc894e6c9bec7bd482be8e',
        repo: 'blog_comment',
        owner: 'tianjindong',
        admin: "tianjindong"
    })
    gitalk.render('comment-container')
</script>

    </div>
</div>
</div>
                




<div class="column is-4-tablet is-3-desktop is-3-widescreen  has-order-1 column-left ">
    
        
<div class="card widget">
    <div class="card-content">
        <nav class="level">
            <div class="level-item has-text-centered">
                <div>
                    
                        <img class="image is-128x128 has-mb-6" src="/images/avatar.png" alt="听到微笑">
                    
                    
                    <p class="is-size-4 is-block">
                        听到微笑
                    </p>
                    
                    
                    <p class="is-size-6 is-block">
                        Java Engineer
                    </p>
                    
                    
                    <p class="is-size-6 is-flex is-flex-center has-text-grey">
                        <i class="fas fa-map-marker-alt has-mr-7"></i>
                        <span>中国 上海</span>
                    </p>
                    
                </div>
            </div>
        </nav>
        <nav class="level is-mobile">
            <div class="level-item has-text-centered is-marginless">
                <div>
                    <p class="heading">
                        文章
                    </p>
                    <p class="title has-text-weight-normal">
                        54
                    </p>
                </div>
            </div>
            <div class="level-item has-text-centered is-marginless">
                <div>
                    <p class="heading">
                        分类
                    </p>
                    <p class="title has-text-weight-normal">
                        20
                    </p>
                </div>
            </div>
            <div class="level-item has-text-centered is-marginless">
                <div>
                    <p class="heading">
                        标签
                    </p>
                    <p class="title has-text-weight-normal">
                        30
                    </p>
                </div>
            </div>
        </nav>
        <div class="level">
            <a class="level-item button is-link is-rounded" href="https://github.com/tianjindong" target="_blank">
                关注我</a>
        </div>
        
        
        <div class="level is-mobile">
            
            <a class="level-item button is-white is-marginless" target="_blank" title="Github" href="https://github.com/tianjindong">
                
                <i class="iconfont-github icon-GitHub"></i>
                
            </a>
            
            <a class="level-item button is-white is-marginless" target="_blank" title="Gitee" href="https://gitee.com/tianjindong">
                
                <i class="iconfont-gitee icon-gitee"></i>
                
            </a>
            
            <a class="level-item button is-white is-marginless" target="_blank" title="CSDN" href="https://blog.csdn.net/tianjindong0804">
                
                <i class="iconfont-csdn icon-CN_csdnnet"></i>
                
            </a>
            
            <a class="level-item button is-white is-marginless" target="_blank" title="Twitter" href="https://twitter.com/HearingSmile">
                
                <i class="iconfont-twitter icon-twitter"></i>
                
            </a>
            
        </div>
        
    </div>
</div>
    
        
<div class="card widget" id="toc">
    <div class="card-content">
        <div class="menu">
            <h3 class="menu-label">
                目录
            </h3>
            <ul class="menu-list"><li>
        <a class="is-flex" href="#HashMap的基本原理">
        <span class="has-mr-6">1</span>
        <span>HashMap的基本原理</span>
        </a></li><li>
        <a class="is-flex" href="#HashMap源码分析">
        <span class="has-mr-6">2</span>
        <span>HashMap源码分析</span>
        </a><ul class="menu-list"><li>
        <a class="is-flex" href="#HashMap中的常量值">
        <span class="has-mr-6">2.1</span>
        <span>HashMap中的常量值</span>
        </a></li><li>
        <a class="is-flex" href="#HashMap中几个关键字段">
        <span class="has-mr-6">2.2</span>
        <span>HashMap中几个关键字段</span>
        </a></li><li>
        <a class="is-flex" href="#构造函数分析">
        <span class="has-mr-6">2.3</span>
        <span>构造函数分析</span>
        </a><ul class="menu-list"><li>
        <a class="is-flex" href="#tableSizeFor方法的作用">
        <span class="has-mr-6">2.3.1</span>
        <span>tableSizeFor方法的作用</span>
        </a></li></ul></li><li>
        <a class="is-flex" href="#静态内部类">
        <span class="has-mr-6">2.4</span>
        <span>静态内部类</span>
        </a></li><li>
        <a class="is-flex" href="#put方法源码">
        <span class="has-mr-6">2.5</span>
        <span>put方法源码</span>
        </a></li><li>
        <a class="is-flex" href="#resize方法">
        <span class="has-mr-6">2.6</span>
        <span>resize方法</span>
        </a></li></ul></li><li>
        <a class="is-flex" href="#总结">
        <span class="has-mr-6">3</span>
        <span>总结</span>
        </a></li></ul>
        </div>
    </div>
</div>

    
        
    
    
        <div class="column-right-shadow  is-sticky">
        
            
<div class="card widget">
    <div class="card-content">
        <h3 class="menu-label">
            最新文章
        </h3>
        
        <article class="media">
            
            <a href="/article/37883.html" class="media-left">
                <p class="image is-64x64">
                    <img class="thumbnail" src="http://image.bigcoder.cn/20210116215841.png" alt="DockerSwarm架构详解(转载)">
                </p>
            </a>
            
            <div class="media-content">
                <div class="content">
                    <div><time class="has-text-grey is-size-7 is-uppercase" datetime="2021-01-16T13:46:04.000Z">2021-01-16</time></div>
                    <a href="/article/37883.html" class="has-link-black-ter is-size-6">DockerSwarm架构详解(转载)</a>
                    <p class="is-size-7 is-uppercase">
                        <a class="has-link-grey -link" href="/categories/Docker/">Docker</a>
                    </p>
                </div>
            </div>
        </article>
        
        <article class="media">
            
            <a href="/article/54308.html" class="media-left">
                <p class="image is-64x64">
                    <img class="thumbnail" src="/gallery/thumbnails/h4.jpg" alt="B树和B+树与磁盘读写之间的联系">
                </p>
            </a>
            
            <div class="media-content">
                <div class="content">
                    <div><time class="has-text-grey is-size-7 is-uppercase" datetime="2019-08-24T02:20:31.000Z">2019-08-24</time></div>
                    <a href="/article/54308.html" class="has-link-black-ter is-size-6">B树和B+树与磁盘读写之间的联系</a>
                    <p class="is-size-7 is-uppercase">
                        <a class="has-link-grey -link" href="/categories/数据结构/">数据结构</a>
                    </p>
                </div>
            </div>
        </article>
        
        <article class="media">
            
            <a href="/article/21035.html" class="media-left">
                <p class="image is-64x64">
                    <img class="thumbnail" src="/gallery/thumbnails/h3.jpg" alt="什么是B+树">
                </p>
            </a>
            
            <div class="media-content">
                <div class="content">
                    <div><time class="has-text-grey is-size-7 is-uppercase" datetime="2019-08-19T10:25:05.000Z">2019-08-19</time></div>
                    <a href="/article/21035.html" class="has-link-black-ter is-size-6">什么是B+树</a>
                    <p class="is-size-7 is-uppercase">
                        <a class="has-link-grey -link" href="/categories/数据结构/">数据结构</a>
                    </p>
                </div>
            </div>
        </article>
        
        <article class="media">
            
            <a href="/article/8567.html" class="media-left">
                <p class="image is-64x64">
                    <img class="thumbnail" src="/gallery/thumbnails/f6.jpg" alt="什么是B-树">
                </p>
            </a>
            
            <div class="media-content">
                <div class="content">
                    <div><time class="has-text-grey is-size-7 is-uppercase" datetime="2019-08-19T10:24:50.000Z">2019-08-19</time></div>
                    <a href="/article/8567.html" class="has-link-black-ter is-size-6">什么是B-树</a>
                    <p class="is-size-7 is-uppercase">
                        <a class="has-link-grey -link" href="/categories/数据结构/">数据结构</a>
                    </p>
                </div>
            </div>
        </article>
        
        <article class="media">
            
            <a href="/article/62369.html" class="media-left">
                <p class="image is-64x64">
                    <img class="thumbnail" src="/gallery/thumbnails/h1.jpg" alt="什么是一致性Hash算法">
                </p>
            </a>
            
            <div class="media-content">
                <div class="content">
                    <div><time class="has-text-grey is-size-7 is-uppercase" datetime="2019-08-16T07:27:10.000Z">2019-08-16</time></div>
                    <a href="/article/62369.html" class="has-link-black-ter is-size-6">什么是一致性Hash算法</a>
                    <p class="is-size-7 is-uppercase">
                        <a class="has-link-grey -link" href="/categories/数据结构/">数据结构</a>
                    </p>
                </div>
            </div>
        </article>
        
    </div>
</div>

        
            
        
        </div>
    
</div>

                
            </div>
        </div>
    </section>
    <footer class="footer">
    <div class="container">
        <div class="level">
            <div class="level-start has-text-centered-mobile">
                <a class="footer-logo is-block has-mb-6" href="/">
                
                    <img src="/images/logo.png" alt="深入解析HashMap源码" height="28">
                
                </a>
                <p class="is-size-7">
                &copy; 2021 听到微笑&nbsp;
                Powered by <a href="https://hexo.io/" target="_blank">Hexo</a> & <a href="https://github.com/ppoffice/hexo-theme-icarus" target="_blank">Icarus</a>
                
                </p>
            </div>
            <div class="level-end">
            
            </div>
        </div>
    </div>
</footer>
    <script src="https://cdn.jsdelivr.net/npm/jquery@3.3.1/dist/jquery.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/moment@2.22.2/min/moment-with-locales.min.js"></script>
<script>moment.locale("zh-CN");</script>


    
    
    
    <script src="/js/animation.js"></script>
    

    
    
    
    <script src="https://cdn.jsdelivr.net/npm/lightgallery@1.6.8/dist/js/lightgallery.min.js" defer></script>
    <script src="https://cdn.jsdelivr.net/npm/justifiedGallery@3.7.0/dist/js/jquery.justifiedGallery.min.js" defer></script>
    <script src="/js/gallery.js" defer></script>
    

    
    

<div id="outdated">
    <h6>Your browser is out-of-date!</h6>
    <p>Update your browser to view this website correctly. <a id="btnUpdateBrowser" href="http://outdatedbrowser.com/">Update
            my browser now </a></p>
    <p class="last"><a href="#" id="btnCloseUpdateBrowser" title="Close">&times;</a></p>
</div>
<script src="https://cdn.jsdelivr.net/npm/outdatedbrowser@1.1.5/outdatedbrowser/outdatedbrowser.min.js" defer></script>
<script>
    document.addEventListener("DOMContentLoaded", function () {
        outdatedBrowser({
            bgColor: '#f25648',
            color: '#ffffff',
            lowerThan: 'flex'
        });
    });
</script>


    
    
<script src="https://cdn.jsdelivr.net/npm/mathjax@2.7.5/unpacked/MathJax.js?config=TeX-MML-AM_CHTML" defer></script>
<script>
document.addEventListener('DOMContentLoaded', function () {
    MathJax.Hub.Config({
        'HTML-CSS': {
            matchFontHeight: false
        },
        SVG: {
            matchFontHeight: false
        },
        CommonHTML: {
            matchFontHeight: false
        },
        tex2jax: {
            inlineMath: [
                ['$','$'],
                ['\\(','\\)']
            ]
        }
    });
});
</script>

    
    

<a id="back-to-top" title="回到顶端" href="javascript:;">
    <i class="fas fa-chevron-up"></i>
</a>
<script src="/js/back-to-top.js" defer></script>


    
    

    
    
    
    

    
    
    
    
    
    <script src="https://cdn.jsdelivr.net/npm/clipboard@2.0.4/dist/clipboard.min.js" defer></script>
    <script src="/js/clipboard.js" defer></script>
    

    
    
    


<script src="/js/main.js" defer></script>

    
    <div class="searchbox ins-search">
    <div class="searchbox-container ins-search-container">
        <div class="searchbox-input-wrapper">
            <input type="text" class="searchbox-input ins-search-input" placeholder="想要查找什么...">
            <span class="searchbox-close ins-close ins-selectable"><i class="fa fa-times-circle"></i></span>
        </div>
        <div class="searchbox-result-wrapper ins-section-wrapper">
            <div class="ins-section-container"></div>
        </div>
    </div>
</div>
<script>
    (function (window) {
        var INSIGHT_CONFIG = {
            TRANSLATION: {
                POSTS: '文章',
                PAGES: '页面',
                CATEGORIES: '分类',
                TAGS: '标签',
                UNTITLED: '(无标题)',
            },
            CONTENT_URL: '/content.json',
        };
        window.INSIGHT_CONFIG = INSIGHT_CONFIG;
    })(window);
</script>
<script src="/js/insight.js" defer></script>
<link rel="stylesheet" href="/css/search.css">
<link rel="stylesheet" href="/css/insight.css">
    
</body>
</html>